Iota and Jot

For other uses of "Jot", see Jot (disambiguation).

Iota and its successor Jot (from Greek iota, Hebrew yodh, the smallest letters in those two alphabets) are Turing tarpits, esoteric programming languages that are designed to be as small as possible but still Turing-complete. Each uses two symbols and involves two operations, with simple denotational semantics defined in terms of lambda calculus. Zot is a continuized version of Iota that includes input and output.

Iota's universal combinator is the lambda term U = \lambda f.((fS)K). Then one can recover the usual SKI basis combinators as follows: I\, =\, (UU),\; K\, =\, (U(U(UU))), \;S\, =\, (U(U(U(UU)))).

Because of its minimalism, it has influenced research concerning Chaitin's constant.[1]

See also

References

  1. ^ Michael Stay, "Very Simple Chaitin Machines for Concrete AIT", Fundamenta Informaticae 68 (3). pp. 231--247 CDMTCS Report 265, 2005

External links